A local area network (LAN) is a system for directly connecting multiple computers so that they can directly exchange information with each other. LANs are considered local because they are designed to connect computers over a small area, such as an office, a building, or a small campus. LANs are considered systems because they are made up of several components, such as cables, repeaters, switches, routers, network interfaces, nodes (computers), and communication protocols. Ethernet is one such protocol. Information is communicated through a LAN in frames transported within data packets. ("Frame" and "data packet," while technically different, are often used interchangeably to describe data carrying the information.)
A LAN switch (or, more generally, a packet switch) is generally defined as a multi-port device that transfers data between its different ports based on the destination addresses and/or other information found in the individual packets it receives. Switches can be used to segment LANs, connect different LANs, or extend the collision diameter of LANs. Switches are of particular importance to Ethernet-based LANs because of their ability to increase network diameter. Additional background information on packet switches can be found in a number of references such as Fast Ethernet (1997) by L. Quinn et al., Computer Networks (3rd Ed. 1996) by A. Tannenbaum, and High-Speed Networking with LAN Switches (1997) by G. Held, all of which are incorporated herein by reference.
There are three common switching architectures used in packet switches for forwarding frames from one port to another: crosspoint (also known as crossbar) matrix, shared bus, and shared memory. A crossbar matrix essentially creates a very transient "circuit" between ports for the duration of a frame (or subset of a frame) exchange. There is an electronic switch located at each crossbar in the matrix between every matrix input and output. A switch controller establishes a direct connection within the switch between two ports, based on the destination address and/or other information within a data packet acquired by the packet's entry port. The packet is then forwarded directly from the entry port (also referred to as the sending port) to an exit port (also referred to as a destination port).
A shared-bus architecture uses a common bus as the exchange mechanism for data packets between ports. Each port (or small group of ports) has its own memory, both for input and output queues, depending on the design.
A shared memory architecture uses a single common buffer memory as the exchange mechanism for frames between ports. All ports access the shared memory via a shared memory bus. An arbitration mechanism, such as time division multiplexing, controls port access to the memory, assuring each entry port a chance to store data that it receives within memory where the exit port can then access it. The buffer memory temporarily stores data packets while routing decisions and re-transmission takes place. Typically, buffer memory is allocated to each port on an as-needed basis from a central pool of buffers, with each allocated buffer returning to the pool when it is no longer needed.
Normal network traffic flow into each port of a switch, however, is bursty in nature, requiring significant amounts of buffer memory for short periods of time but requiring little or no memory at other times. This characteristic makes it desirable to allow any switch port to acquire as much available shared memory as needed. But an unmanaged "take all you need," or "first come, first served" memory allocation scheme can lead to unregulated overflow of memory usage. This scheme can result in sporadic discards or chaotic generation of flow control messages on several branches of the network as incoming traffic has nowhere to be stored.
An objective of the invention, therefore, is to flow control or discard incoming traffic on only those ports that are consuming excessive amounts of buffer memory and leave unaffected the traffic flow between non-offending ports. More particularly, an objective of the invention is to provide a simple, cost-effective method for regulating the buffer memory requested by a port in a shared memory switching device.